package com.mamingchao.foundation.tree.heap;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;

/**
 * Created by mlamp on 2024/5/24.
 * 开发语言自带的堆结构设计，如果已经生成大根堆，然后再更新其中一个node 的value，大根堆 会被破坏为 非大根堆结构。因为没有触发【重新构造大根堆】
 * 不是不可以支持，而是支持这个记住每个 node 在更新node value之前的 index，即在堆中的位置索引；在不确定大部分使用堆结构的开发者，是不是都需要这个功能的前提下
 * 开发语言设计者  设计的不支持 动态更新开发语言自带的 堆结构 node value更新
 *
 *
 * 基于大根堆的形式开发
 */
public class MyHeap<T> {

    // 堆数据存储载体，动态的数组
    private ArrayList<T> heap;
    // 记录每个node 在堆中的索引位置
    private HashMap<T, Integer> heapIndexRecorder;

    private int heapSize;
    // 自定义对比器
    private Comparator<T> comparator;

    public MyHeap(Comparator<T> comparator) {
        this.heap = new ArrayList<>();
        this.heapIndexRecorder = new HashMap<>();
        this.comparator = comparator;
    }

    public int size(){
        return heapSize;
    }

    public boolean isEmpty(){
        return heapSize == 0;
    }

    public boolean contain(T node){
        return heap.indexOf(node) > 0;
    }


    /**
     *  返回大根堆的root 节点，并在返回后删除；把树的最后叶子节点放到root 根位置，然后再heapify 成大根堆
     * @return 返回的大根堆的root 节点
     */
    public T poll(){
        T element = this.peek();
        heap.set(0, heap.get(heapSize - 1));
        heap.remove(heapSize-1);
        heapSize --;
        this.heapify(heap,0);

        return element;
    }

    /**
     * 更新已存在的节点值
     */
    public void updExistElement(T node) {
        if (!heapIndexRecorder.containsKey(node))
            throw new RuntimeException("该项数据不存在，如想添加，请使用put方法");

        int myIndex = heapIndexRecorder.get(node);
        heap.add(myIndex, node);

        this.heapInsert(heap, myIndex);
        this.heapify(heap,myIndex);

        int freshIndex = heap.indexOf(node);
        heapIndexRecorder.put(node,freshIndex);

    }


    /**
     * 追加节点，并且 调整为大根堆
     * @param node
     */
    public void put(T node){
        heap.add(node);
        this.heapInsert(heap, heapSize);
        heapSize ++;

    }


    public T peek(){
        if (heapSize == 0) {
            return null;
        }
        return heap.get(0);
    }


    /**
     * 从当前节点的index一直向上到整个树的root，check；如果node value 大，上浮
     * 基于大根堆的堆结构，设计
     * @param heap 堆数组
     * @param appendNodeIndex  当前的节点的index
     */
    private void heapInsert(ArrayList<T> heap, int appendNodeIndex){
        if (appendNodeIndex <=0) {
            return;
        }

        int parentNodeIndex = (appendNodeIndex-1)/2;

        while (comparator.compare(heap.get(parentNodeIndex), heap.get(appendNodeIndex)) > 0) {
            swapArrayList(heap, appendNodeIndex, parentNodeIndex);
            appendNodeIndex = parentNodeIndex;
            parentNodeIndex = (appendNodeIndex-1)/2;
        }
    }


    /**
     * 从当前节点的index一直向下到树的叶子节点，check；如果node value 小，下沉
     * 基于大根堆的堆结构，设计
     * @param arr 堆数组
     * @param curNodeIndex 当前的节点的index
     */
    private void heapify(ArrayList<T> arr, int curNodeIndex){
        if (curNodeIndex <0) {
            return;
        }


        int maxValueChildIndex = curNodeIndex;
        while (curNodeIndex < heapSize) {

            int leftChildNodeIndex = 2 * curNodeIndex + 1;
            int rightChildNodeIndex = leftChildNodeIndex + 1;


            // 如果有左孩子，即如果 当前node不是叶子节点，返回左节点的index
            if(leftChildNodeIndex < heapSize && comparator.compare(heap.get(curNodeIndex), heap.get(leftChildNodeIndex)) > 0)
                maxValueChildIndex = leftChildNodeIndex;

            // 如果 右孩子也存在，并且右孩子比左孩子的value还大，则返回右孩子的index
            if (rightChildNodeIndex < heapSize && comparator.compare(heap.get(leftChildNodeIndex), heap.get(rightChildNodeIndex)) > 0){
                maxValueChildIndex = rightChildNodeIndex;
            }

            if (maxValueChildIndex != curNodeIndex){
                swapArrayList(arr, maxValueChildIndex, curNodeIndex);
                curNodeIndex = maxValueChildIndex;
            } else {
                break;
            }
        }
    }


    /**
     * 系统自带 ArrayList 元素
     */
    private void swapArrayList(ArrayList<T> heap, int i, int j) {
        T temp = heap.get(i);
        heap.set(i, heap.get(j));
        heapIndexRecorder.put(heap.get(j),i);
        heap.set(j, temp);
        heapIndexRecorder.put(temp,j);
    }


}
